package ru.qiwi.security;

import java.util.Random;

/**
 * ���������� ������� ����������. ������ ����� ��� ��������� � �����
 * ��������� ��������� ���������� �� ���������� � ������������� ���������
 * (J2ME CDC platform, MIDP 2.0 profile) � ����������������� ���������.
 * � ����� � ���� ���� ������� ����������� �������, �� ���������������
 * � ����������. ���������� ������ ���� �������� ������������ ��� ���������
 * ��������� (�������� ������ ��������� ������ {@link #modPow(BigInteger, BigInteger)},
 * ������� ��� ��������� � �������������� �������������� ����� ��������� ��������.
 * <b>��������������: ��� ���������� �� ������������ ������������� �����.</b>
 * ���� ��� ��� ���������� ��� ����������� �������� ������ (���� � ��������������).
 * <p>���������� �������� �� ����� ru.eport.handler.BigInteger Warren Levy <warrenl@cygnus.com>,
 * ���������� � ������� 1999 ����, �������, � ���� �������, ������������ ��
 * ���������� IntNum.java BitOps.java by Per Bothner <per@bothner.com>
 * (found in Kawa 1.6.62), � ����� ������������ Java Platform 1.2 API Specification,
 * "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) �
 * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996).
 *
 * @author Maxim Karvonen
 * @ date ���� 2006
 * @ status ���������� �� ���������� � ����� ���������������� �������
 */

class BigInteger
{
    
 

	/**
	 * Compare x[0:size-1] with y[0:size-1], treating them as unsigned integers.
	 *
	 * @result -1, 0, or 1 depending on if x<y, x==y, or x>y.
	 * This is basically the same as gmp's mpn_cmp function.
	 */
	private static int cmp( int[] x, int[] y, int size )
	{
		//Absolutely correct for unsigned. Max Karvonen
		while( --size >= 0 )
		{
			int x_word = x[size];
			int y_word = y[size];
			if( x_word != y_word )
			{
				// Invert the high-order bit, because:
				// (unsigned) X > (unsigned) Y iff
				// (int) (X^0x80000000) > (int) (Y^0x80000000).
				return ( x_word ^ 0x80000000 ) > ( y_word ^ 0x80000000 ) ? 1 : -1;
			}
		}
		return 0;
	}

	/**
	 * Compare x[0:xlen-1] with y[0:ylen-1], treating them as unsigned integers.
	 *
	 * @result -1, 0, or 1 depending on if x<y, x==y, or x>y.
	 */
	static int cmp( int[] x, int xlen, int[] y, int ylen )
	{
		return xlen > ylen ? 1 : xlen < ylen ? -1 : cmp( x, y, xlen );
	}

	/**
	 * ���������� ��������� �������� ������ �� ����������� �����
	 *
	 * @param dest ������-���������
	 * @param x		���������
	 * @param len	����� ���������
	 * @param y		������ ���������
	 * @return ��������� �������� ����� ��������� (������� ������)
	 */
	static int mul_1( int[] dest, int[] x, int len, int y )
	{
		long yword = ( long ) y & 0xffffffffL;
		long carry = 0;
		for( int j = 0; j < len; j++ )
		{
			carry += ( ( long ) x[j] & 0xffffffffL ) * yword;
			dest[j] = ( int ) carry;
			carry >>>= 32;
		}
		return ( int ) carry;
	}

	/**
	 * ��������� ��������� ���� ��������
	 *
	 * @param dest ������-���������
	 * @param x		������ ���������
	 * @param xlen ����� ������� ���������
	 * @param y		������ ���������
	 * @param ylen ����� ������� ���������
	 */
	static void mul( int[] dest, int[] x, int xlen, int[] y, int ylen )
	{
//    dest[xlen] = mul_1 (dest, x, xlen, y[0]);

		for( int i = 0; i < ylen; i++ )
		{
			long yword = ( long ) y[i] & 0xffffffffL;
			long carry = 0;
			for( int j = 0; j < xlen; j++ )
			{
				carry += ( ( long ) x[j] & 0xffffffffL ) * yword + ( ( long ) dest[i + j] & 0xffffffffL );
				dest[i + j] = ( int ) carry;
				carry >>>= 32;
			}
			dest[i + xlen] = ( int ) carry;
		}
	}

	/**
	 * ��������� �������� ������������ � ����������
	 *
	 * @param dest	 ���������, ���������
	 * @param x			���������
	 * @param dstLen ����� ����������
	 * @param len		����� ���������
	 * @param y			���������
	 * @return ���������� �������� ���� � ����������
	 */
	static int mulAdd_1( int [] dest, int [] x, int dstLen, int len, int y )
	{
		long yword = ( long ) y & 0xffffffffL;
		long carry = 0;
		int j;
		for( j = 0; j < len; j++ )
		{
			//�������� ������������
			carry += ( ( long ) x[j] & 0xffffffffL ) * yword + ( ( long ) dest[j] & 0xffffffffL );
			dest[j] = ( int ) carry;
			carry >>>= 32;
		}
		while( carry != 0 )
		{
			carry += ( ( long ) dest[j] & 0xffffffffL );
			dest[j] = ( int ) carry;
			carry >>>= 32;
			j++;
		}
		return j > dstLen ? j : dstLen; //����� ����� ����������
	}

	/**
	 * ���������� � ��������� ������������ ���� ������� �����
	 *
	 * @param dest	 ���������, ���������
	 * @param x			������ ���������
	 * @param xlen	 ����� ������� ���������
	 * @param y			������ ���������
	 * @param ystart �������� ������� ���������
	 * @param ylen	 ����� ������� ���������
	 */
	static void mulAdd( int[] dest, int[] x, int xlen, int[] y, int ystart, int ylen )
	{
		// dest[xlen] = mul_1 (dest, x, xlen, y[0]);

		for( int i = 0; i < ylen; i++ )
		{
			long yword = ( long ) y[ystart + i] & 0xffffffffL;
			long carry = 0;
			for( int j = 0; j < xlen; j++ )
			{
				carry += ( ( long ) x[j] & 0xffffffffL ) * yword + ( ( long ) dest[i + j] & 0xffffffffL );
				dest[i + j] = ( int ) carry;
				carry >>>= 32;
			}
			carry += dest[i + xlen] & 0xffffffffL;
			dest[i + xlen] = ( int ) carry;
			carry >>>= 32;
			if( carry > 0 )
			{
				int cpos;
				for( cpos = i + xlen + 1; dest[cpos] == -1; cpos++ )
				{
					dest[cpos] = 0;
				}
				dest[cpos]++; //increment!
			}
		}
	}

/*  public static int divmod_1 (int[] quotient, int[] dividend,
															int len, int divisor)
	{
		int i = len - 1;
		long r = dividend[i];
		if ((r & 0xffffffffL) >= ((long)divisor & 0xffffffffL))
			r = 0;
		else
		{
			quotient[i--] = 0;
			r <<= 32;
		}

		for (;  i >= 0;  i--)
		{
			int n0 = dividend[i];
			r = (r & ~0xffffffffL) | (n0 & 0xffffffffL);
			r = udiv_qrnnd (r, divisor);
			quotient[i] = (int) r;
		}
		return (int)(r >>> 32);
	}*/

	/**
	 * ������� ����� ������� �����
	 *
	 * @param i ����� ��� �������� �����
	 * @return ����� ������� �������� �����
	 */
	static int count_leading_zeros( int i )
	{
		if( i == 0 )
		{
			return 32;
		}
		int count = 0;
		for( int k = 16; k > 0; k = k >> 1 )
		{
			int j = i >>> k;
			if( j == 0 )
			{
				count += k;
			}
			else
			{
				i = j;
			}
		}
		return count;
	}

	/**
	 * Shift x[0:len-1] left by count bits, and store the len least
	 * significant words of the result in dest[d_offset:d_offset+len-1].
	 * Return the bits shifted out from the most significant digit.
	 * Assumes 0 < count < 32.
	 * OK if dest==x.
	 */
	static int lshift( int[] dest, int d_offset, int[] x, int len, int count )
	{
		int count_2 = 32 - count;
		int i = len - 1;
		int high_word = x[i];
		int retval = high_word >>> count_2;
		d_offset++;
		while( --i >= 0 )
		{
			int low_word = x[i];
			dest[d_offset + i] = ( high_word << count ) | ( low_word >>> count_2 );
			high_word = low_word;
		}
		dest[d_offset + i] = high_word << count;
		return retval;
	}

	/**
	 * ��������� ������ ����� �����
	 *
	 * @param dest		������ ��� ����������
	 * @param x			 �������� ������
	 * @param x_start ��������� ��������
	 * @param len		 ����� ��������� �������
	 * @param count	 ����� ������
	 * @return ������� (���������) ����
	 */
	static int rshift( int[] dest, int[] x, int x_start, int len, int count )
	{
		int count_2 = 32 - count;
		int low_word = x[x_start];
		int retval = low_word << count_2;
		int i = 1;
		for( ; i < len; i++ )
		{
			int high_word = x[x_start + i];
			dest[i - 1] = ( low_word >>> count ) | ( high_word << count_2 );
			low_word = high_word;
		}
		dest[i - 1] = low_word >>> count;
		return retval;
	}

	/**
	 * ��������� ������ ����� � ����������� �����
	 *
	 * @param dest		������ ��� ���������� ����������
	 * @param x			 �������� �����
	 * @param x_start ��������� �������
	 * @param len		 ����� ��������� �����
	 * @param count	 �������� ������
	 */
	static void rshift0( int[] dest, int[] x, int x_start, int len, int count )
	{
		if( count > 0 )
		{
			rshift( dest, x, x_start, len, count );
		}
		else
		{
			for( int i = 0; i < len; i++ )
			{
				dest[i] = x[i + x_start];
			}
		}
	}


	/**
	 * ��������� ������� �������� ����� �� �����.
	 *
	 * @param N �������
	 * @param D ��������
	 * @return ������� �����, ��� ������� 32 ���� - ������� �� �������, ������� 32 ���� - �������
	 */
	static long udiv_qrnnd( long N, int D )
	{
//    long q, r;
//    long a1 = N >>> 32;
//    long a0 = N & 0xffffffffL;
//    if (D >= 0)
//    {
//      if (a1 < ((D - a1 - (a0 >>> 31)) & 0xffffffffL))
//      {
//        /* dividend, divisor, and quotient are nonnegative */
//        q = N / D;
//        r = N % D;
//      }
//      else
//      {
//        /* Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d */
//        long c = N - ((long) D << 31);
//        /* Divide (c1*2^32 + c0) by d */
//        q = c / D;
//        r = c % D;
//        /* Add 2^31 to quotient */
//        q += 1 << 31;
//      }
//    }
//    else
//    {
//      long b1 = D >>> 1;	/* d/2, between 2^30 and 2^31 - 1 */
//      //long c1 = (a1 >> 1); /* A/2 */
//      //int c0 = (a1 << 31) + (a0 >> 1);
//      long c = N >>> 1;
//      if (a1 < b1 || (a1 >> 1) < b1)
//      {
//        if (a1 < b1)
//        {
//          q = c / b1;
//          r = c % b1;
//        }
//        else /* c1 < b1, so 2^31 <= (A/2)/b1 < 2^32 */
//        {
//          c = ~(c - (b1 << 32));
//          q = c / b1;  /* (A/2) / (d/2) */
//          r = c % b1;
//          q = (~q) & 0xffffffffL;    /* (A/2)/b1 */
//          r = (b1 - 1) - r; /* r < b1 => new r >= 0 */
//        }
//        r = 2 * r + (a0 & 1);
//        if ((D & 1) != 0)
//        {
//          if (r >= q)
//          {
//            r = r - q;
//          }
//          else if (q - r <= ((long) D & 0xffffffffL))
//          {
//            r = r - q + D;
//            q -= 1;
//          }
//          else
//          {
//            r = r - q + D + D;
//            q -= 2;
//          }
//        }
//      }
//      else /* Implies c1 = b1 */
//      {
//        /* Hence a1 = d - 1 = 2*b1 - 1 */
//        if (a0 >= ((long)(-D) & 0xffffffffL))
//        {
//          q = -1;
//          r = a0 + D;
//        }
//        else
//        {
//          q = -2;
//          r = a0 + D + D;
//        }
//      }
//    }
//      return (r << 32) | (q & 0xffffffffL);
		long d1 = D & 0xffffffffL;
		if( N >= 0 )
		{
			long q = N / d1;
			long r = N % d1;
			return ( r << 32 ) + q;
		}
		else
		{
			long v1 = N >>> 1;
			long q = v1 / d1;
			long r = v1 % d1;
			q <<= 1;
			r = ( r << 1 ) | ( N & 1L );
			q += r / d1;
			r %= d1;
			return ( r << 32 ) + q;
		}
	}

	/**
	 * ��������� ������� �������� ����� �� ������ ������� �����. �������
	 * ����������� ������ ����� � ������� ����� 0
	 *
	 * @param divisible �������, ������ ��� ����������
	 * @param divisibleLen	����� ��������� �����
	 * @param divisor	 ��������
	 * @param divisorLen	����� ��������
	 * @noinspection SuspiciousNameCombination
	 */

	static void divide( int[] divisible, int divisibleLen, int[] divisor, int divisorLen )
	{
		// This is basically Knuth's formulation of the classical algorithm,
		// but translated from in scm_divbigbig in Jaffar's SCM implementation.

		// Correspondance with Knuth's notation:
		// Knuth's u[0:m+n] == divisible[divisibleLen:0].
		// Knuth's v[1:n] == divisor[divisorLen-1:0]
		// Knuth's n == divisorLen.
		// Knuth's m == divisibleLen-divisorLen.
		// Our divisibleLen == Knuth's m+n.

		// Could be re-implemented using gmp's mpn_divrem:
		// divisible[divisibleLen] = mpn_divrem (&divisible[divisorLen], 0, divisible, divisibleLen, divisor, divisorLen).

		int j = divisibleLen;
		do
		{													// loop over digits of quotient
			// Knuth's j == our divisibleLen-j.
			// Knuth's u[j:j+n] == our divisible[j:j-divisorLen].
			int qhat;	// treated as unsigned
			//note, that in any case it's impossible to divisible[j] > divisor[divisorLen-1] by
			//start assumption(leading zero) or by the induction
			if( divisible[j] == divisor[divisorLen - 1] )
			{
				qhat = -1;	// 0xffffffff - big number!
			}
			else
			{
				long w = ( ( ( long ) ( divisible[j] ) ) << 32 ) + ( ( long ) divisible[j - 1] & 0xffffffffL );
				qhat = ( int ) udiv_qrnnd( w, divisor[divisorLen - 1] ); //divisible[j] < divisor[divisorLen-1] => qhat fits into int
			}
			if( qhat != 0 )
			{
				int borrow = submul_1( divisible, j - divisorLen, divisor, divisorLen, qhat );
				//number to substract from divisible[j];
				int save = divisible[j];
				long num = ( ( long ) save & 0xffffffffL ) - ( ( long ) borrow & 0xffffffffL );
				//if substraction was successfull num == 0, in other case we should decrease qhat
				//and add substracted number
				//note, that if num != 0, then num = -1:
				//divisor = divisor[divisorLen-1] << 32 + r, (divisor[divisorLen-1] << 32) * what < divisible
				//=> r * what <= r << 32, and it can't cnahge directly on high word
				//of divisible (only by carry flag from divisible[j-1])
				while( num != 0 )
				{
					qhat--;
					long carry = 0;
					for( int i = 0; i < divisorLen; i++ )
					{
						carry += ( ( long ) divisible[j - divisorLen + i] & 0xffffffffL ) + ( ( long ) divisor[i] & 0xffffffffL );
						divisible[j - divisorLen + i] = ( int ) carry;
						carry >>>= 32;
					}
					//divisible[j] += carry; it's not necessary, it will be disposed after loop
					num = carry - 1;
				}
			}
			divisible[j] = qhat;
		}
		while( --j >= divisorLen );
	}

/*public static long add_n (int dest[], int[] x, int[] y, int len)
  {
    long carry = 0;
    for (int i = 0; i < len;  i++)
    {
      carry += ((long) x[i] & 0xffffffffL)
               + ((long) y[i] & 0xffffffffL);
      dest[i] = (int) carry;
      carry >>>= 32;
    }
    return carry;
  }*/

	/**
	 * Subtract x[0:len-1]*y from dest[offset:offset+len-1].
	 * All values are treated as if unsigned.
	 *
	 * @return the most significant word of
	 *         the product, minus borrow-out from the subtraction.
	 */
	static int submul_1( int[] dest, int offset, int[] x, int len, int y )
	{
		long yl = ( long ) y & 0xffffffffL;
		int carry = 0;
		int j = 0;
		do
		{
			long prod = ( ( long ) x[j] & 0xffffffffL ) * yl;
			int prod_low = ( int ) prod;
			int prod_high = ( int ) ( prod >> 32 );
			prod_low += carry;
			// Invert the high-order bit, because: (unsigned) X > (unsigned) Y
			// iff: (int) (X^0x80000000) > (int) (Y^0x80000000).
			carry = ( ( prod_low ^ 0x80000000 ) < ( carry ^ 0x80000000 ) ? 1 : 0 ) + prod_high;
			int x_j = dest[offset + j];
			prod_low = x_j - prod_low;
			if( ( prod_low ^ 0x80000000 ) > ( x_j ^ 0x80000000 ) )
			{
				carry++;
			}
			dest[offset + j] = prod_low;
		}
		while( ++j < len );
		return carry;
	}

	/**
	 * ���������� ����� � ����� ��� ������ �����
	 *
	 * @param i �����
	 * @return ���������� ����� ��� ������ �����
	 */
	static int intLength( int i )
	{
		return 32 - count_leading_zeros( i );
	}

	/**
	 * ���������� ����� � ����� �������� �����
	 *
	 * @param words ������ ��� �������� �����
	 * @param len	 ����� ������� (���������� �������� ���)
	 * @return ���������� ���, ����������� ��� ������ �������� �����
	 */
	static int intLength( int[] words, int len )
	{
		len--;
		return intLength( words[len] ) + 32 * len;
	}

	/**
	 * ������� ���������� ������������� ���
	 *
	 * @param words ������ ��� ������ ����������� ����
	 * @return ����� ����������� �������������� ����
	 */
	static int findLowestBit( int[] words )
	{
		for( int i = 0; ; i++ )
		{
			if( words[i] != 0 )
			{
				return 32 * i + findLowestBit( words[i] );
			}
		}
	}

	/**
	 * ������� ���������� ������������� ���
	 *
	 * @param word ����� ��� ������ ����������� ����
	 * @return ����� ����������� �������������� ����
	 */
	static int findLowestBit( int word )
	{
		int i = 0;
		while( ( word & 0xF ) == 0 )
		{
			word >>= 4;
			i += 4;
		}
		if( ( word & 3 ) == 0 )
		{
			word >>= 2;
			i += 2;
		}
		if( ( word & 1 ) == 0 )
		{
			i += 1;
		}
		return i;
	}

/* static int gcd (int[] x, int[] y, int len)
  {
    int i, word;
    // Find sh such that both x and y are divisible by 2**sh.
    for (i = 0; ; i++)
    {
      word = x[i] | y[i];
      if (word != 0)
      {
        // Must terminate, since x and y are non-zero.
        break;
      }
    }
    int initShiftWords = i;
    int initShiftBits = findLowestBit (word);
    // Logically: sh = initShiftWords * 32 + initShiftBits

    // Temporarily divide both x and y by 2**sh.
    len -= initShiftWords;
    ru.eport.handler.MPN.rshift0 (x, x, initShiftWords, len, initShiftBits);
    ru.eport.handler.MPN.rshift0 (y, y, initShiftWords, len, initShiftBits);

    int[] odd_arg; /* One of x or y which is odd. 
    int[] other_arg; /* The other one can be even or odd. 
    if ((x[0] & 1) != 0)
    {
      odd_arg = x;
      other_arg = y;
    }
    else
    {
      odd_arg = y;
      other_arg = x;
    }

    for (;;)
    {
      // Shift other_arg until it is odd; this doesn't
      // affect the gcd, since we divide by 2**k, which does not
      // divide odd_arg.
      for (i = 0; other_arg[i] == 0; )
        i++;
      if (i > 0)
      {
        int j;
        for (j = 0; j < len-i; j++)
          other_arg[j] = other_arg[j+i];
        for ( ; j < len; j++)
          other_arg[j] = 0;
      }
      i = findLowestBit(other_arg[0]);
      if (i > 0)
        ru.eport.handler.MPN.rshift (other_arg, other_arg, 0, len, i);

      // Now both odd_arg and other_arg are odd.

      // Subtract the smaller from the larger.
      // This does not change the result, since gcd(a-b,b)==gcd(a,b).
      i = ru.eport.handler.MPN.cmp(odd_arg, other_arg, len);
      if (i == 0)
        break;
      if (i > 0)
      { // odd_arg > other_arg
        ru.eport.handler.MPN.sub_n (odd_arg, odd_arg, other_arg, len);
        // Now odd_arg is even, so swap with other_arg;
        int[] tmp = odd_arg;
        odd_arg = other_arg;
        other_arg = tmp;
      }
      else
      { // other_arg > odd_arg
        ru.eport.handler.MPN.sub_n (other_arg, other_arg, odd_arg, len);
      }
      while (odd_arg[len-1] == 0 && other_arg[len-1] == 0)
        len--;
    }
    if (initShiftWords + initShiftBits > 0)
    {
      if (initShiftBits > 0)
      {
        int sh_out = ru.eport.handler.MPN.lshift (x, initShiftWords, x, len, initShiftBits);
        if (sh_out != 0)
          x[(len++)+initShiftWords] = sh_out;
      }
      else
      {
        for (i = len; --i >= 0;)
          x[i+initShiftWords] = x[i];
      }
      for (i = initShiftWords;  --i >= 0; )
        x[i] = 0;
      len += initShiftWords;
    }
    return len;
  }*/

	/**
	 * Subtract Y[0:size-1] from X[0:size-1], and write
	 * the size least significant words of the result to dest[0:size-1].
	 * Return borrow, either 0 or 1.
	 * This is basically the same as gmp's mpn_sub_n function.
	 */

	static int sub_n( int[] dest, int[] X, int[] Y, int size )
	{
		int cy = 0;
		for( int i = 0; i < size; i++ )
		{
			int y = Y[i];
			int x = X[i];
			y += cy;	/* add previous carry to subtrahend */
			// Invert the high-order bit, because: (unsigned) X > (unsigned) Y
			// iff: (int) (X^0x80000000) > (int) (Y^0x80000000).
			cy = ( y ^ 0x80000000 ) < ( cy ^ 0x80000000 ) ? 1 : 0;
			y = x - y;
			cy += ( y ^ 0x80000000 ) > ( x ^ 0x80000000 ) ? 1 : 0;
			dest[i] = y;
		}
		return cy;
	}

/* static int set_str (int dest[], byte[] str, int str_len, int base)
	{
		int size = 0;
		if ((base & (base - 1)) == 0)
		{
			// The base is a power of 2.  Read the input string from
			// least to most significant character/digit.

			int next_bitpos = 0;
			int bits_per_indigit = 0;
			for (int i = base; (i >>= 1) != 0; )
				bits_per_indigit++;
			int res_digit = 0;

			for (int i = str_len;  --i >= 0; )
			{
				int inp_digit = str[i];
				res_digit |= inp_digit << next_bitpos;
				next_bitpos += bits_per_indigit;
				if (next_bitpos >= 32)
				{
					dest[size++] = res_digit;
					next_bitpos -= 32;
					res_digit = inp_digit >> (bits_per_indigit - next_bitpos);
				}
			}

			if (res_digit != 0)
				dest[size++] = res_digit;
		}
		else
		{
			// General case.  The base is not a power of 2.
			int indigits_per_limb = ru.eport.handler.MPN.chars_per_word (base);
			int str_pos = 0;

			while (str_pos < str_len)
			{
				int chunk = str_len - str_pos;
				if (chunk > indigits_per_limb)
					chunk = indigits_per_limb;
				int res_digit = str[str_pos++];
				int big_base = base;

				while (--chunk > 0)
				{
					res_digit = res_digit * base + str[str_pos++];
					big_base *= base;
				}

				int cy_limb;
				if (size == 0)
					cy_limb = res_digit;
				else
				{
					cy_limb = ru.eport.handler.MPN.mul_1 (dest, dest, size, big_base);
					cy_limb += ru.eport.handler.MPN.add_1 (dest, dest, size, res_digit);
				}
				if (cy_limb != 0)
					dest[size++] = cy_limb;
			}
		}
		return size;
	}*/

/* static int add_1 (int[] dest, int[] x, int size, int y)
  {
    long carry = (long) y & 0xffffffffL;
    for (int i = 0;  i < size;  i++)
    {
      carry += ((long) x[i] & 0xffffffffL);
      dest[i] = (int) carry;
      carry >>= 32;
    }
    return (int) carry;
  }*/

/*static int chars_per_word (int radix)
  {
    if (radix < 10)
    {
      if (radix < 8)
      {
        if (radix <= 2)
          return 32;
        else if (radix == 3)
          return 20;
        else if (radix == 4)
          return 16;
        else
          return 18 - radix;
      }
      else
        return 10;
    }
    else if (radix < 12)
      return 9;
    else if (radix <= 16)
      return 8;
    else if (radix <= 23)
      return 7;
    else if (radix <= 40)
      return 6;
    // The following are conservative, but we don't care.
    else if (radix <= 256)
      return 4;
    else
      return 1;
  }*/

	
    
    
	/**
	 * ���������� �������� �������� (32-������ �����) � {@link #words},
	 * ���� ���� �������� �����, ���������� ��� 32-������ ����������� �����.
	 *
	 * @see BigInteger#words words
	 */
	private transient int ival;
	/**
	 * ����� "����", ������������ ������ ������� �����. ������� �������
	 * ����� ������� ������. ������ ����� �������� 32-������ �����������
	 * ����� ������. ���� ���� ����� <code>null</code>, �� �������� ��������
	 * ����� �������� � {@link #ival}. ���� �������� �� ����� <code>null</code>,
	 * �� ������ {@link #ival} ���� ���������� �������� ����� �������� �����.
	 * <p>��� ������������� ��������� ������������ ������������ ���. �����, ���
	 * ������ ������� ���������� 32 ���, ������ �������� �
	 * ���� {@link #ival} � ����� ���� {#words} ������ <code>null</code>. ���
	 * ��������� ����� �������� � ������� {#words} � ��� ���� ��������
	 * <code>words[ival]</code> �� ����� 0. �� ������ ������ ����� {#words} 
	 * �� ������ �������� {@link #ival} (�� ����� ���� � ������).
	 */
	private transient int[] words;

	/**
	 * ����������� ������� ����������� �����.
	 *
	 * @see #maxFixNum
	 * @see #numFixNum
	 * @see #smallFixNums
	 */
	private static final int minFixNum = 0;
	/**
	 * ������������ ������� ����������� �����
	 *
	 * @see #minFixNum
	 * @see #numFixNum
	 * @see #smallFixNums
	 */
	private static final int maxFixNum = 8;
	/**
	 * ���������� ������� ����������� �����
	 *
	 * @see #minFixNum
	 * @see #maxFixNum
	 * @see #smallFixNums
	 */
	private static final int numFixNum = maxFixNum + 1;
	/**
	 * ������� ����������� ����� �����. ������������ ��� ��������������
	 * �������� �������� ���������� ���������� ��������.
	 *
	 * @see #minFixNum
	 * @see #maxFixNum
	 * @see #numFixNum
	 */
	private static final BigInteger[] smallFixNums = new BigInteger[numFixNum];

	static
	{
		for( int i = numFixNum; --i >= 0; )
		{
			smallFixNums[i] = new BigInteger(i);
		}
	}

	/**
	 * ������������� ���������� ����������. ���� ���������� � false,
	 * �� ��� ������ ������ ������� ������������� InterruptedException
	 */
	static volatile boolean active = true;
	//void stop() { active = false; }

	/**
	 * ������� ��������� ������� �����. ������������ � �������� ��������
	 * ��� �������� (���������) ������ ����������.
	 */
	static final int[] primes = {
              2,   3,   5,   7,  11,  13,  17,  19,  23,  29,
             31,  37,  41,  43,  47,  53,  59,  61,  67,  71,
             73,  79,  83,  89,  97, 101, 103, 107, 109, 113,
            127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
            179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
            233, 239, 241, 251};
	
	/**
	 * ������� ����������� ���� ����� ����� ������ �������� ����� modPow ��� ����, ����� �� ����� ��������� �� ��������� ������ ����, �����
	 * ��� ���� ����� ������� ������� ����� �������� ����������, ����������� �� �������� ����� ������
	 */
	private static final int TIME_HACK_MOTOROLA_FREEING_THREAD = 1;

	/**
	 * HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4.
	 */
	private BigInteger()
	{
	}

	/* Create a new (non-shared) ru.eport.handler.BigInteger, and initialize to an unsigned int. */
	private BigInteger( int value )
	{
		ival = value;
	}

	/**
	 * ������� ����� ������� ����� �� ������� ����. ��� �������� ������
	 * ��������������� ��� ������� �����, � ������� ������� ��������
	 * ������������� ������� �������� ������� �������.
	 *
	 * @param val �������� ������ �������� �����
	 */
	BigInteger( byte[] val )
	{
		if( val == null || val.length < 1 )
		{
			throw new NumberFormatException();
		}

		int bptr = 0;
		while( bptr < val.length && val[bptr] == 0 )
		{
			bptr++;
		}

		if( bptr == val.length )
		{
			return; //value is zero, and by default ival = 0, words = null
		}
		if( val.length - bptr <= 4 )
		{
			//���������� ������ �����.
			int res = 0;
			while( bptr < val.length )
			{
				res = res << 8 | ( val[bptr++] & 0xff );
			}
			ival = res;
			return;
		}

		int byteLen = val.length - bptr;
		int nwords = ( byteLen + 3 ) / 4;
		ival = nwords;
		words = new int[ival];
		int word = 0;
		for( int i = byteLen % 4; i > 0; i-- )
		{
			word = word << 8 | ( val[bptr++] & 0xff );
		}
		if( 0 != byteLen % 4 )
		{
			words[--nwords] = word;
		}
		while( nwords > 0 )
		{
			words[--nwords] = val[bptr++] << 24 | ( val[bptr++] & 0xff ) << 16 | ( val[bptr++] & 0xff ) << 8 | ( val[bptr++] & 0xff );
		}
	}

	/**
	 * ������� ��������� ������� �����, ��������� �� ��������� ���������� ����
	 * (32-������ ���������). ��� ���������� ������ �������� <code>words</code> ������
	 * ���� ������ 1.
	 *
	 * @param rnd	 - ��������� ��������� ����� ��� ������������� � �������� ������
	 * @param words - ���������� ����, ������� ������ ���� � ��������� ������� �����
	 */
	BigInteger( Random rnd, int words )
	{
		this.ival = words;
		this.words = new int[words];
		regenerate( rnd );
	}

	/**
	 * ������������������ ����� ���������� ����������. ����� ������ ����� ���������
	 * � ������ ���������. ��������������, ��� ����� ����� ���������� ��� ����������
	 * �������� �������� ����� � ����� �� ���������� ���������� �������
	 *
	 * @param rnd - ��������� ��������� ����� ��� ������������� ��� �����������
	 */
	void regenerate( Random rnd )
	{
		int wordsLength = words.length;
		for( int i = 0; i < wordsLength; i++ )
		{
			words[i] = rnd.nextInt();
		}
	}

	/**
	 * ���������� �������� (�������� �����������), ���������������
	 * ���������� �����. ������� ����� ���������� ��� �����������
	 *
	 * @param val �����, �������� �������� �������
	 * @return ������� �����, ����������� �� �������� � <code>val</code>
	 */
	static BigInteger valueOf( long val )
	{
		if( val >= minFixNum && val <= maxFixNum )
		{
			return smallFixNums[((int) val)];
		}
		int i = ( int ) ( val >>> 32 ); //high 32 bits of the val
		BigInteger result = new BigInteger();
		if( 0 == i )
		{
			result.ival = ( int ) val;
		}
		else
		{
			result.ival = 2;
			result.words = new int[2];
			result.words[0] = ( int ) val; //low 32 bits of the val
			result.words[1] = i; //high 32 bits of the val
		}
		return result;
	}

	/**
	 * ���������� �������� (�������� �����������), ���������������
	 * ���������� �����. ������� ����� ���������� ��� �����������
	 *
	 * @param val �����, �������� �������� �������
	 * @return ������� �����, ����������� �� �������� � <code>val</code>
	 */
	static BigInteger valueOf( int val )
	{
		if( val >= 0 && val <= maxFixNum )
		{
			return smallFixNums[val];
		}
		return new BigInteger( val );
	}

	/**
	 * ���������, �������� �� ������� ����� �����. ��������� ������
	 * � ������������ ������.
	 *
	 * @return true, ���� ����� �������� �����, false � ��������� ������
	 */
	boolean isZero()
	{
		return ival == 0;// && words[0] == 0;
	}

	/**
	 * ���������, �������� �� ������� ����� ��������. ��������� ������
	 * � ������������ ������.
	 *
	 * @return true, ���� ����� �������� ��������, false � ��������� ������
	 */
	boolean isOne()
	{
		return ival == 1;// && (words[0] == 1);
	}

	/**
	 * ���������� ������������ ������������� �������� �����
	 *
	 * @return ������������ ������������� �����
	 */
	private BigInteger canonicalize()
	{
		if( words == null )
		{
			if( ival >= minFixNum && ival <= maxFixNum )
			{
				return smallFixNums[ival];
			}
			else
			{
				return this;
			}
		}
		while( ival > 0 && words[ival - 1] == 0 )
		{
			ival--;
		}
		if( ival <= 1 )
		{
			ival = words[0];
			words = null;
			if( ival >= minFixNum && ival <= maxFixNum )
			{
				return smallFixNums[ival];
			}
		}
		return this;
	}

	/**
	 * ���������� �������� �������� �����, ������������ �� �������.
	 * �������� ��������� ������ � �������, �������������� 2:32+2
	 *
	 * @return �������� <code>(this - 1)</code>
	 */
	BigInteger subtractOne()
	{
		BigInteger res = new BigInteger();

		res.words = new int[ival]; //this is quite good length
		int pos = 0;
		while( pos < ival && words[pos] == 0 )
		{
			res.words[pos++] = -1;
		}
		res.words[pos] = words[pos] - 1;
		pos++;
		if( pos == ival )
		//if decremented digit was 1 at fisrt pos, then we should dec length
		{
			res.ival = ( words[pos - 1] == 1 ) ? ival - 1 : ival;
		}
		else
		{
			System.arraycopy( words, pos, res.words, pos, ival - pos );
			res.ival = ival;
		}
		return res;
	}

	/**
	 * ������� ������������ ���� ������� �����. �������� ���������
	 * ������ � ������ x >= 2^32, y >= 2^32.
	 *
	 * @param x ���������
	 * @param y ���������
	 * @return ������������ x * y
	 */
	static BigInteger times( BigInteger x, BigInteger y )
	{
/*		if (y.words == null)
			return times(x, y.ival);
		if (x.words == null)
			return times(y, x.ival);*/

		int[] xwords;
		int[] ywords;
		int xlen = x.ival;
		int ylen = y.ival;
		xwords = x.words;
		ywords = y.words;

		// Swap if x is shorter then y.
		if( xlen < ylen )
		{
			int[] twords = xwords;
			xwords = ywords;
			ywords = twords;
			int tlen = xlen;
			xlen = ylen;
			ylen = tlen;
		}
		BigInteger result = new BigInteger();
		result.words = new int[xlen + ylen];
		 mul( result.words, xwords, xlen, ywords, ylen );
		result.ival = xlen + ylen;
		return result.canonicalize();
	}

	/**
	 * ��������� ������� �� ������� this �� y. this � y ������ ����
	 * � ������������ �����
	 *
	 * @param y ��������
	 * @return ������� �� ������� this �� y
	 */
	private BigInteger mod( BigInteger y )
	{
		if( this.words == null )
		{
			if( y.words != null ) //y > x
			{
				return this;
			}
			long v1l = ( this.ival & 0xffffffffL );
			long v2l = ( y.ival & 0xffffffffL );
			return valueOf( ( int ) ( v1l / v2l ) );
		}

		int ylen = y.ival;
		int xlen = this.ival;
		//we need a leading zero during divizion phase for
		//a successful start.
		int[] xwords = new int[xlen + 2];
		System.arraycopy( this.words, 0, xwords, 0, xlen );
		int [] ywords = y.words; //= new int[ylen];
		//System.arraycopy(y.words, 0, ywords, 0, ylen);

		int cmpval =  cmp( xwords, xlen, ywords, ylen );
		if( cmpval < 0 ) // abs(x) < abs(y)
		{
			return this;
		}
		if( cmpval == 0 ) // abs(x) == abs(y) (x == y)
		{
			return smallFixNums[0];
		}
		// Normalize the denominator, i.e. make its most significant bit set by
		// shifting it normalization_steps bits to the left.  Also shift the
		// numerator the same number of steps (to keep the quotient the same!).
		int nshift =  count_leading_zeros( ywords[ylen - 1] );
		if( nshift != 0 )
		{
			// Shift up the denominator setting the most significant bit of
			// the most significant word.
			ywords = new int[ylen];
			 lshift( ywords, 0, y.words, ylen, nshift );

			// Shift up the numerator, possibly introducing a new most
			// significant word.
			int x_high =  lshift( xwords, 0, xwords, xlen, nshift );
			xwords[xlen++] = x_high;
		}

		xlen++; //in any case, we need a leading zero!
		 divide( xwords, xlen, ywords, ylen );
		//shift the remainder
		if( nshift != 0 )
		{
			 rshift0( xwords, xwords, 0, ylen, nshift );
		}
		while( ylen > 1 && xwords[ylen] == 0 )
		{
			ylen--;
		}
		if( 1 == ylen )
		{
			return valueOf( xwords[0] );
		}
		BigInteger res = new BigInteger();
		res.ival = ylen;
		res.words = xwords; //don't relocate arrays, this bigints are only temporary objects
		return res;
	}

	/**
	 * ��������� ��������� �������� ����� �� ����������� �����.
	 *
	 * @param value �����, �� ������� ����������� ���������
	 * @return 0 == this mod value
	 */
	boolean divides( int value )
	{
		long divisor = value & 0xffffffffL;
		long carry = 0;
		for( int i = ival; --i >= 0; )
		{
			carry = ( carry << 32 ) + ( words[i] & 0xffffffffL );
			carry %= divisor;
		}
		return 0 == carry;
	}

	/**
	 * ��������� �������� ����� ��� this �� ������ mod. �������� ������
	 * � ��������� this � mod � ����� ��������� �������� mod &gt; this
	 * (������������� ��� ������������� ������ � �������
	 * ������������).<br>
	 * ��� ���������� ������������ ���������������� ��������
	 * �������, ��� ��������� ���� � ������������ � ������ ������ ��
	 * ������������� �����.<br>
	 * �������� �������� � �������� ���� (a, b, ca, cb, S), ��� S
	 * - ���� �����, ������ ��������, ��� ��������� �������� - �����.
	 * �������� �������� �������� � ������� (this, mod, 1, 0, false).
	 * � �������� ������ ��������� ����������� ��������� ����:<ol>
	 * <li>���� a = 1, �� �������� ����������� � ����������� (S ? mod - ca, ca).
	 * <li>���� a = 0, �� �������� ����������� � ������� ���(a, b) &gt1; 1
	 * <li>���� a &lt; b, �� ����������� ����� (a, b, ca, cb, S) -&gt;
	 * (b, a, bc, ca, not S)
	 * <li>���� a &gt;= b, �� ����������� �������������� ����
	 * (a, b, ca, cb, S) -&gt; (a % b, b, ca + (a / b) * cb, S).
	 * </ol>
	 * <b>����������� ���������.</b><br>
	 * ������������� ��������� ������� �� ����������� �������� � �����������������
	 * ��� ���������� ����������� ��������������, � ����� �� ������������� ���������� ����
	 * ������� ������.
	 * ���������� ������ ��������� � ����������������� �������� ����� ����
	 * (a, b, ca, cb, ca1, cb1, S) = V. ���������� ������ ����� �������������
	 * ����� (this, mod, 1, 0, 0, 1, 1). ��������� ��������� ��������� �������������
	 * ��������� ��������:<ol>
	 * <li>������� ���������� (-1 == S) ? (mod - ca) : ca.
	 * <li>���������� � ������� (�� ��������� ������� ���(this, mod) &gt; 1);
	 * <li>�������������� (a, b, ca, cb, ca1, cb1, S) -&gt; (b, a, cb, ca, cb1, ca1, -S)
	 * <li>�������������� (a, b, ca, cb, ca1, cb1, S) -&gt;
	 * (a % b, b, ca + (b / a) * cb, cb, ca1 + (b / a) * cb1, cb1, -S);
	 * </ol>
	 * ����� �������� � �������� ������ ���������� ������ V<sub>i</sub>, i &gt; 0,
	 * � �������� ���������� ������ ������������ V<sub>0</sub>, ���
	 * V<sub>i</sub> = (a<sub>i</sub>, b<sub>i</sub>, ca<sub>i</sub>, cb<sub>i</sub>,
	 * ca1<sub>i</sub>, cb1<sub>i</sub>, S<sub>i</sub>). ����� ����������� ��������� �����������:
	 * <ol><li> ��� �������� V<sub>i</sub> �� ����������� S<sub>i</sub> �� ������������,
	 * S<sub>i</sub> ��������� �������� +/-1;
	 * <li> a<sub>i</sub> = S<sub>i</sub> * (a<sub>0</sub> * ca<sub>i</sub> - b<sub>0</sub> * ca1<sub>i</sub>)
	 * <br> b<sub>i</sub> = -S<sub>i</sub> * (a<sub>0</sub> * cb<sub>i</sub> - b<sub>0</sub> * cb1<sub>i</sub>)
	 * <li> a<sub>i</sub> * cb<sub>i</sub> + b<sub>i</sub> * ca<sub>i</sub> = b<sub>0</sub>
	 * </ol>
	 * ����������� 1 �������� �� �������������� ��� ������� � ��������� �������.<br>
	 * ����������� 2 ������������ ��-��������. ���� �������� (i = 0) ����������� ���������������.
	 * �������. ���� ������� ����������� �� 3-�� ������ ���������, �� ����������� �����������<br>
	 * a<sub>i+1</sub> = b<sub>i</sub> = -S<sub>i</sub> * (a<sub>0</sub> * cb<sub>i</sub>
	 * - b<sub>0</sub> * cb1<sub>i</sub>) = S<sub>i+1</sub> * (a<sub>0</sub> * ca<sub>i+1</sub>
	 * - b<sub>0</sub> * ca1<sub>i+1</sub>) (� ���� S<sub>i+1</sub> = -S<sub>i</sub>,
	 * ca<sub>i+1</sub>=cb<sub>i</sub>, ca1<sub>i+1</sub>=cb1<sub>i</sub>).<br>
	 * b<sub>i+1</sub> = a<sub>i</sub> =  S<sub>i</sub> * (a<sub>0</sub> * ca<sub>i</sub>
	 * - b<sub>0</sub> * ca1<sub>i</sub>) = -S<sub>i+1</sub> * (a<sub>0</sub> * cb<sub>i+1</sub>
	 * - b<sub>0</sub> * cb1<sub>i+1</sub>)(� ���� S<sub>i+1</sub> = -S<sub>i</sub>,
	 * cb<sub>i+1</sub>=ca<sub>i</sub>, cb1<sub>i+1</sub>=ca1<sub>i</sub>).<br>
	 * ���� ������� ����������� �� 4-�� ������ ���������, �� ����������� �����������<br>
	 * r = a<sub>i</sub> % b<sub>i</sub>, d = a<sub>i</sub> / b<sub>i</sub><br>
	 * a<sub>i+1</sub> = r = a<sub>i</sub> - b<sub>i</sub> * d =
	 * S<sub>i</sub> * (a<sub>0</sub> * ca<sub>i</sub> - b<sub>0</sub> * ca1<sub>i</sub>)
	 * + S<sub>i</sub> * (a<sub>0</sub> * cb<sub>i</sub> - b<sub>0</sub> * cb1<sub>i</sub>) * d =
	 * S<sub>i</sub> * (a<sub>0</sub> * (ca<sub>i</sub> + d * cb<sub>i</sub>) -
	 * b<sub>0</sub> * (ca1<sub>i</sub> - cb1<sub>i</sub> * d)) =
	 * S<sub>i+1</sub> * (a<sub>0</sub> * ca<sub>i+1</sub> - b<sub>0</sub> * ca1<sub>i+1</sub>) <br>
	 * � ���� ����������� <br>
	 * S<sub>i+1</sub>=S<sub>i</sub><br>
	 * ca<sub>i+1</sub> = ca<sub>i</sub> + d * cb<sub>i</sub><br>
	 * ca1<sub>i+1</sub> = ca1<sub>i</sub> + d * cb1<sub>i</sub><br>
	 * ��� b<sub>i+1</sub> ����������� ����������� �������������. ����� �������,
	 * ����������� �����. <br>
	 * ����������� 3 ���� ������������ ��-��������. ���� �������� (i = 0) �����������
	 * ���������������.
	 * �������. ���� ������� ����������� �� 3-�� ������ ���������, �������� ���������� ��������. ����
	 * ������� ����������� �� 4-�� ������ ���������, ��<br>
	 * r = a<sub>i</sub> % b<sub>i</sub>, d = a<sub>i</sub> / b<sub>i</sub><br>
	 * a<sub>i+1</sub> = r = a<sub>i</sub> - b<sub>i</sub> * d<br>
	 * b<sub>i+1</sub> = b<sub>i</sub>
	 * ca<sub>i+1</sub> = ca<sub>i</sub> + d * cb<sub>i</sub><br>
	 * cb<sub>i+1</sub> = cb<sub>i</sub><br>
	 * a<sub>i+1</sub> * cb<sub>i+1</sub> + b<sub>i+1</sub> * ca<sub>i+1</sub> =
	 * (a<sub>i</sub> - b<sub>i</sub>*d) * cb<sub>i</sub> + b<sub>i</sub> *
	 * (ca<sub>i</sub> + d * cb<sub>i</sub> =
	 * a<sub>i</sub> * cb<sub>i</sub> - b<sub>i</sub> * cb<sub>i</sub> * d +
	 * b<sub>i</sub> * ca<sub>i</sub> + b<sub>i</sub> * cb<sub>i</sub> * d =
	 * a<sub>i</sub> * cb<sub>i</sub> + b<sub>i</sub> * ca<sub>i</sub> = b<sub>0</sub> <br>
	 * ����� �������, ����������� 4 �����.<br>
	 * ��� �������� ���������� ��������� ����������� �����������
	 * 1 = a<sub>k</sub> = S<sub>k</sub> * (ca<sub>k</sub> * a<sub>0</sub> -
	 * ca1<sub>k</sub> * b<sub>0</sub>). ��� ��� b<sub>0</sub> = mod, ��
	 * S<sub>k</sub> * ca<sub>k</sub> *a<sub>0</sub> == 1 (mod mod), � ��� ���
	 * a<sub>0</sub> = this, �� this * (S<sub>k</sub> * ca<sub>k</sub>) == 1(mod mod)
	 * � (S<sub>k</sub> * ca<sub>k</sub>) = this ^ -1 (mod mod). ����� ����, �� ���. 1
	 * S<sub>k</sub> = +1, �� ���. 4 � ���. 1
	 * mod = b<sub>0</sub> >= a<sub>k</sub> * ca<sub>k</sub> = ca<sub>k</sub>, �.�.
	 * ����������� � ��������� �������� ����� ������ � ������� [0, mod-1], ��� � ����������� ��������.
	 *
	 * @param mod - ������, �� �������� ������������ ����������
	 * @return - �����, �����, ��� ��� ��������� �� this ���
	 *         ��� ������� �� mod ������� 1.
	 * @throws ArithmeticException - ���� this � mod ��
	 *                             �������� ���������������.
	 */

	BigInteger modInverse( BigInteger mod )
	{
		int [] aWords;
		int [] bWords;
		int [] caWords;
		int [] cbWords;
		boolean negative;
		int aLen, bLen, caLen, cbLen;
		//������������� ���������, ����� ��������� ������ ��� - �����
		bLen = this.words == null ? 1 : this.ival;
		aLen = mod.words == null ? 1 : mod.ival;
		aWords = new int[aLen + 1]; //���������� ��� ������ �������, 0 �� ������ ������
		bWords = new int[bLen + 1];
		if( this.words != null )
		{
			System.arraycopy( this.words, 0, bWords, 0, bLen );
		}
		else
		{
			bWords[0] = this.ival;
		}
		if( mod.words != null )
		{
			System.arraycopy( mod.words, 0, aWords, 0, aLen );
		}
		else
		{
			aWords[0] = mod.ival;
		}
		caLen = cbLen = 1;
		//����� �� ����������� ����� mod, ��. �������� ���������
		caWords = new int[aLen + 1]; //for null
		cbWords = new int[aLen + 1]; //for null
		cbWords[0] = 1;
		negative = true;
		do
		{
			//����������� ����� ������ � � � �� ���� 3-�� ������ ���������
			if( bLen == 1 && bWords[0] == 0 ) //����� 2
			{
				throw new ArithmeticException( "not invertible" );
			}
			if( bLen == 1 && bWords[0] == 1 ) //����� 1
			{
				break;
			}
			if( aLen == 1 )
			{ //bLen == 1
				long wA = ( aWords[0] & 0xffffffffL );
				long wB = ( bWords[0] & 0xffffffffL );
				aWords[0] = ( int ) ( wA % wB );
				//fast mul
				caLen =  mulAdd_1( caWords, cbWords, caLen, cbLen, ( int ) ( wA / wB ) );
			}
			else
			{
				aWords[aLen] = 0; //���������� ��� ����������� �������
				 divide( aWords, aLen, bWords, bLen );
				//������ aWords ������ ������� � �������.
				//reminder = aWords[0..bLen-1];
				//quotient = aWords[bLen..aLen]
				//perform ca = ca + cb * (a / b);
				 mulAdd( caWords, cbWords, cbLen, aWords, bLen, aLen - bLen + 1 );
				caLen = cbLen + aLen - bLen + 1;
				while( caLen > 1 && caWords[caLen - 1] == 0 )
				{
					caLen--;
				}

				aLen = bLen;
				while( aLen > 1 && aWords[aLen] == 0 )
				{
					aLen--;
				}
				//reminder = aWords[0..aLen-1]
			}
			//3-� ����� ���������
			negative = !negative;
			int tmp = aLen;
			aLen = bLen;
			bLen = tmp;
			tmp = caLen;
			caLen = cbLen;
			cbLen = tmp;
			int [] tmp1 = aWords;
			aWords = bWords;
			bWords = tmp1;
			tmp1 = caWords;
			caWords = cbWords;
			cbWords = tmp1;
		}
		while( true );
		//note extra change
		caWords = cbWords;
		caLen = cbLen;
		if( !negative )
		{
			caLen = ( mod.words == null ) ? 1 : mod.ival;
			if( mod.words == null )
			{
				caWords[0] = mod.ival;
			}
			else
			{
				 sub_n( caWords, mod.words, caWords, caLen );
			}
			while( caLen > 1 && caWords[caLen - 1] == 0 )
			{
				caLen--;
			}
		}
		if( caLen == 1 )
		{
			return valueOf( caWords[0] );
		}
		BigInteger res = new BigInteger();
		res.words = new int[caLen];
		res.ival = caLen;
		System.arraycopy( caWords, 0, res.words, 0, caLen );
		return res;
	}

	/**
	 * ��������� �������� this ** exponent % mod. mod ���������� ���
	 * ����������� �����.
	 *
	 * @param exponent �������
	 * @param mod			������
	 * @return �������� (this ** exponent % mod)
	 */
	private BigInteger modPowLight( BigInteger exponent, int mod )
	{
		long thisVal;
		long mlong = ( mod & 0xffffffffL );
		if( words == null )
		{
			thisVal = ( ival & 0xffffffffL ) % mlong;
		}
		else
		{
			int i = ival - 1;
			long r = words[i];
			if( ( r & 0xffffffffL ) >= mlong )
			{
				r = 0;
			}
			else
			{
				r <<= 32;
				i--;
			}

			for( ; i >= 0; i-- )
			{
				int n0 = words[i];
				r = ( r & ~0xffffffffL ) | ( n0 & 0xffffffffL );
				r =  udiv_qrnnd( r, mod );
			}
			thisVal = ( r >>> 32 );
		}
		long res = 1; //���������
		if( exponent.words == null )
		{
			int cv = exponent.ival;
			while( cv != 0 )
			{
				if( 0 != ( cv & 1 ) )
				{
					res =  udiv_qrnnd( res * thisVal, mod );
				}
				thisVal =  udiv_qrnnd( thisVal * thisVal, mod );
				cv >>>= 1;
			}
			return valueOf( res );
		}
		//general case, there is some words in exponent
		int [] words = exponent.words;
		int wlen = exponent.ival;
		while( wlen > 0 && 0 == words[wlen - 1] )
		{
			wlen--;
		}
		for( int i = 0; i < wlen; i++ )
		{
			int cword = words[i];
			for( int j = 0; j < 32; j++ )
			{ //32 bits in 1 int
				if( 0 != ( cword & 1 ) )
				{
					res =  udiv_qrnnd( res * thisVal, mod );
				}
				thisVal =  udiv_qrnnd( thisVal * thisVal, mod );
				cword >>>= 1;
			}
		}
		return valueOf( res );
	}

	/**
	 * ����������� ��� ����� �� ������ modBytes. ������� ��������� ��������� � ������ ������, ����������
	 * ����� ����������, ���������� � ������ �������.
	 *
	 * @param dst				 ���� �� ����������, � ����� ������ ��� �������� ����������
	 * @param dstLen			����� ������� ���������
	 * @param src				 ������ ���������
	 * @param srcLen			����� ������� ���������
	 * @param mulBuf			����� ��� �������� ���������� ���������
	 * @param modBytes		�������� (������) �����
	 * @param modLen			����� �������� (� ������)
	 * @param shiftLength ����� ������ ��� ���������� ������� (����� �������� ����������� �����
	 *                    �����, ����� - ������)
	 * @return ����� �������� ��� � ���������� ���������� �������� �������
	 */
	private int mulMod( int [] dst, int dstLen, int[] src, int srcLen, int [] mulBuf, int [] modBytes, int modLen, int shiftLength )
	{
		int productLength = dstLen + srcLen;
		if( dstLen == 1 )
		{
			mulBuf[srcLen /*productLength-1*/] =  mul_1( mulBuf, src, srcLen, dst[0] );
		}
		else if( srcLen == 1 )
		{
			mulBuf[dstLen /*productLength - 1*/] =  mul_1( mulBuf, dst, dstLen, src[0] );
		}
		else
		{
			for( int i = 0; i < mulBuf.length; i++ )
			{
				mulBuf[i] = 0;
			}
			 mul( mulBuf, src, srcLen, dst, dstLen );
		}
		//now mulBuf contains product of two numbers
		while( productLength > 1 && mulBuf[productLength - 1] == 0 )
		{
			productLength--;
		}
		if( shiftLength != 0 )
		{
			mulBuf[productLength] =  lshift( mulBuf, 0, mulBuf, productLength, shiftLength );
		}
		else
		{
			mulBuf[productLength] = 0;
		}

		productLength++; //zero byte, or shifted bytes
		//note, that by this shift hith word of mulBuf is less than high word of modBytes (high bit is zero 
		//product, but modBytes has high bit set to one)
//		out(dst, dstLen);
//		out(src, srcLen);
//		out(mulBuf, productLength);
		if( productLength <= modLen )
		{
			//see comment later, if product have same length, as divider,
			//then product is less, than divider
			System.arraycopy( mulBuf, 0, dst, 0, productLength );
			return mulBuf[productLength - 1] == 0 ? productLength - 1 : productLength;
		}
		 divide( mulBuf, productLength - 1, modBytes, modLen ); //yes, -1, it's a last index, not length
		dstLen = modLen; //reminder!
		while( dstLen > 1 && mulBuf[dstLen - 1] == 0 )
		{
			dstLen--;
		}
		if( shiftLength == 0 )
		{
			System.arraycopy( mulBuf, 0, dst, 0, dstLen );
		}
		else
		{
			 rshift( dst, mulBuf, 0, shiftLength, dstLen );
			if( dstLen > 1 && dst[dstLen - 1] == 0 )
			{
				dstLen--;
			}
		}
		return dstLen;
	}

	/**
	 * ��������� �������� this ** exponent mod m
	 *
	 * @param exponent ���������� �������
	 * @param m				������
	 * @return this ** exponent % m
	 * @throws InterruptedException ���� � �������� ������ ��� �������� �����
	 */
	BigInteger modPow( BigInteger exponent, BigInteger m ) throws InterruptedException
	{
//		m = m.canonicalize(); //skip zeroes, etc...
//		exponent = exponent.canonicalize();
		if( !active )
		{
			throw new InterruptedException();
		}
		if( m.isZero() )
		{
			throw new ArithmeticException( "non-positive modulo" );
		}

		//   if (exponent.isNegative())
		//     return modInverse(m);
		if( exponent.isOne() )
		{
			return mod( m );
		}

		if( exponent.isZero() )
		{
			return smallFixNums[1];
		}

		// To do this naively by first raising this to the power of exponent
		// and then performing modulo m would be extremely expensive, especially
		// for very large numbers.  The solution is found in Number Theory
		// where a combination of partial powers and moduli can be done easily.
		//
		// We'll use the algorithm for Additive Chaining which can be found on
		// p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier.
/*		ru.eport.handler.BigInteger s = ONE;
		ru.eport.handler.BigInteger t = this;
		ru.eport.handler.BigInteger u = exponent;
		int[] mem = new int[m.ival * 2];

		while (!u.isZero()) {
//			u.out();
//			if (u.and(ONE).isOne())
			if (u.isZeroBitSet()) {
//                System.err.println("IsOne");
				s = timesmod(s, t, m, mem);
//				s.out();
			}
			u = u.shiftRight(1);
//			u.out();
			t = timesmod(t, t, m, mem);
//			t.out();
		}

		return s;*/
		if( m.words == null ) //light case, integer and long math. is sufficient
		{
			return modPowLight( exponent, m.ival );
		}

		BigInteger start = this.mod( m ); //��������� ��������, ������� m �� ������

		int [] mwords; //��������, ��� ������������� - ���������
		int shiftLength =  count_leading_zeros( m.words[m.ival - 1] );
		//shiftLength != 32 (m.words[m.ival-1] != 0);
		if( shiftLength == 0 )
		{
			mwords = m.words;
		}
		else
		{
			mwords = new int[m.ival];
			 lshift( mwords, 0, m.words, m.ival, shiftLength );
		}

		int resultCount = 1;
		int [] resultWords = new int[m.ival]; //���������� ����������
		resultWords[0] = 1;

		int [] powWords = new int[m.ival]; //������� ���������
		int powCount;
		if( start.words == null )
		{
			powCount = 1;
			powWords[0] = start.ival;
		}
		else
		{
			powCount = start.ival;
			System.arraycopy( start.words, 0, powWords, 0, powCount );
		}

		/*
				 * ��� �������� ������������ ���������� ����� 2*m.ival.
				 * ��� ������������ �������� ������� ���������� ��� ���� ��������
				 * �����. � ���������� ��������� ���������� ����� ����� �������� 0
				 * ����� ������ ��� �� ����� ����� ������� � ������� ������� (�����
				 * ������ �� ������ 31), ��� ���������� ��� ��������� �������.
				 */
		int [] tmp = new int[m.ival * 2 + 1];

		int [] expWords = exponent.words;
		int expLength = expWords == null ? 1 : exponent.ival;
		expLength--; //��������� ����� ������������� ��������
		for( int i = 0; i < expLength; i++ )
		{
			int eWord = expWords[i];
			if( !active )
			{
				throw new InterruptedException();
			}
			for( int j = 0; j < 32; j++ )
			{//��������� �����
				if( 0 != ( eWord & 1 ) )
				{
					resultCount = mulMod( resultWords, resultCount, powWords, powCount, tmp, mwords, m.ival, shiftLength );
				}
				powCount = mulMod( powWords, powCount, powWords, powCount, tmp, mwords, m.ival, shiftLength );
				//out(powWords, powCount);
				eWord >>>= 1;
			}
			//������ �������, ������ ��� ��� �������� ��� �� ��������� ������� (��������, ���������) ��� ���� ��������� �������� ��� ���������,
			//������� �������� ����� ���������.
			try
			{
				Thread.sleep( TIME_HACK_MOTOROLA_FREEING_THREAD );
			}
			catch( Exception ignored)
			{

			}
		}

		//��������� ���������� �����, ������ exponent = 0 ��� ���������, �.�. ���� �������� �������
		if( !active )
		{
			throw new InterruptedException();
		}
		int lastWord = ( expWords == null ) ? exponent.ival : expWords[expLength];
		do
		{
			if( 0 != ( lastWord & 1 ) )
			{
				resultCount = mulMod( resultWords, resultCount, powWords, powCount, tmp, mwords, m.ival, shiftLength );
			}
			lastWord >>>= 1;
//			System.err.println(lastWord);
			if( lastWord != 0 ) //�������� ���� ���������
			{
				powCount = mulMod( powWords, powCount, powWords, powCount, tmp, mwords, m.ival, shiftLength );
			}
//			out(powWords, powCount);
		}
		while( lastWord != 0 );

		if( resultCount == 1 )
		{
			return valueOf( resultWords[0] );
		}
		BigInteger result = new BigInteger();
		result.ival = resultCount;
		result.words = new int[resultCount];
		System.arraycopy( resultWords, 0, result.words, 0, resultCount );

		return result;
	}

	/**
	 * ��������� ����������� ����� ������.
	 *
	 * @param count �������� ������
	 */
	void setShiftRight( int count )
	{
		if( count == 0 )
		{
			return;
		}
		int word_count = count >> 5;
		count &= 31;
		int d_len = ival - word_count;
		 rshift0( words, words, word_count, d_len, count );
	}

	public int hashCode()
	{
		// FIXME: May not match hashcode of JDK.
		return ival == 1 ? words[0] : ( words[0] + words[ival - 1] );
	}

	/**
	 * Calculates ceiling(log2(this &lt; 0 ? -this : this+1))
	 * See Common Lisp: the Language, 2nd ed, p. 361.
	 *
	 * @return ���������� �����, ����������� ��� ������ �����
	 */
	int bitLength()
	{
		if( words == null )
		{
			return  intLength( ival );
		}
		return  intLength( words, ival );
	}

	/**
	 * ���������� �������� ������������� �������� �����
	 *
	 * @return �������� ������������� �����
	 */
	byte[] toByteArray()
	{
		// Determine number of bytes needed.  The method bitlength returns
		// the size without the sign bit, so add one bit for that and then
		// add 7 more to emulate the ceil function using integer math.

        //byte[] bytes = new byte[( bitLength()  + 7 ) / 8];
        byte[] bytes = new byte[ 512 / 8 ] ;
        // TODO
        /*
            ������ "�������" ��������� ��� �� ��������, ��� ������� ��������������� ������� ����������� �������� 63 ��� ����� ����.
            ����� ��� ����� �������� �������� response result=202 �� �������, �.�. ������� ��������� � 63 � ����� ����,
               ��������������, ��� base64 ��������� ���������� 63 �����

          */




		int nbytes = bytes.length;

		int wptr = 0;
		int word;

		// Deal with words array until one word or less is left to process.
		// If ru.eport.handler.BigInteger is an int, then it is in ival and nbytes will be <= 4.
		while( nbytes > 4 )
		{
			word = words[wptr++];
			for( int i = 4; i > 0; --i, word >>= 8 )
			{
				bytes[--nbytes] = ( byte ) word;
			}
		}

		// Deal with the last few bytes.  If ru.eport.handler.BigInteger is an int, use ival.
		word = ( words == null ) ? ival : words[wptr];
		for( ; nbytes > 0; word >>= 8 )
		{
			bytes[--nbytes] = ( byte ) word;
		}

		return bytes;
	}

	/**
	 * ���������� ������� �����, �������� ���������� �� �����
	 *
	 * @param mask ������� �����
	 * @return (this AND mask)
	 */
	int getLowBitsMask( int mask )
	{
		return ( words != null ? words[0] : ival ) & mask;
	}

	/**
	 * ������������� ������� ��� �������� �����
	 */
	void setZeroBit()
	{
		if( null == words )
		{
			ival |= 1;
		}
		else
		{
			words[0] |= 1;
		}
	}

	/**
	 * ���������� ������ ����������� �������������� ����
	 *
	 * @return ������ ����������� �������������� ����
	 */
	int getLowestSetBit()
	{
/*		if (isZero())
			return -1;
		if (words == null)
			return ru.eport.handler. findLowestBit(ival);*/
		return  findLowestBit( words );
	}

	/**
	 * ���������� �� ��������� ��� �����
	 *
	 * @param a ����� ��� ���������
	 * @return this == a
	 */
	boolean equalsto( BigInteger a )
	{
		if( this.ival != a.ival )
		{
			return false;
		}

		if( this.words == null )
		{
			return true; //canonical view for this and a
		}

		for( int i = 0; i < this.ival; i++ )
		{
			if( this.words[i] != a.words[i] )
			{
				return false;
			}
		}
		return true;
	}

	/**
	 * ������������� ���� � ������� ����� �����
	 *
	 * @param mask ���� ��� ���������
	 */
	void orHighWord( int mask )
	{
		if( words == null )
		{
			this.ival |= mask;
		}
		else
		{
			this.words[this.ival - 1] |= mask;
		}
	}

}
